Turbo-codes have received considerable attention since their introduction in 1993. This is due to their powerful error correcting capability, reasonable complexity, and flexibility in terms of accommodating different block lengths and code rates.
Interleaving is a key component of Turbo-codes. FIG. 1 illustrates a conventional Turbo-code encoder with two rate ½ encoders. A source (not shown) provides symbols di to a first recursive systematic convolutional (RSC) encoder 100, and to an interleaver 102, which interleaves the symbols and provides the interleaved copy to the second RSC encoder 104. The output from encoders 100 and 104 is provided to a puncturer 106 which punctures the parity symbols generated by the RSC encoders. The puncturer 106 may optionally puncture some of the source data symbols. The source symbols di and corresponding punctured parity symbols pi are both provided, as the encoded codeword, to the modulator which is not shown.
Two interleaver types that have been commonly investigated are the “random” interleaver and the so-called “S-random” or “spread” interleaver. It is known in the art that good spreading properties are desirable for both fast convergence during iterative decoding and maintenance of good distance properties between codewords. More recent high-spread interleavers include dithered golden interleavers, and low extrinsic correlation interleavers. Methods of generating high-spread random (HSR) interleavers are known. In a paper entitled “New High-Spread High-Distance Interleavers for Turbo-codes” presented at 20th Biennial Symposium on Communications, Kingston Ontario, Canada by S. Crozier, pp. 3-7, May 28-31 2000, a method of developing high spread interleavers was disclosed. This method also uses a more natural and effective definition of spread that is closely related to the distance properties of Turbo-codes. The same spread definition is used here. The HSR method, along with distance spectrum testing and index shuffling to eliminate low-weight codewords (post-processing), has provided some of the best performance results to date. The HSR method is used herein as one performance benchmark and is fully described in Canadian Patent Application No. 2,348,941 to Crozier.
The above described interleaver design methods typically require that all Kb indices be stored to implement a single interleaver of length Kb. This is not a major concern when only one interleaver is required, as the other memory requirements for the corresponding Turbo-code encoder and decoder are also of order Kb. However, when a bank of B interleavers is required to accommodate B different block lengths, and B is on the order of the longest interleaver length, KB, then the interleaver bank memory requirements become order KB2. This can be prohibitive, especially if KB is many thousands of bits. This is referred to as the interleaver bank problem.
In general, there are several criteria that a good interleaver bank should satisfy. The bank should provide a wide range of interleaver lengths, for example from a few tens of bits to many thousands of bits, depending on the application. The bank should have good resolution with convenient interleaver lengths. For example, the lengths could increase by 1 or 2 bits for short lengths (tens of bits), by a single byte (8 bits) for medium lengths (hundreds of bits), or by a few bytes for long lengths (thousands of bits). The amount of memory required to define and store each interleaver should be low. Ideally, there should only be a few parameters per interleaver length. The algorithm used to generate the interleaver indexes should also be simple. If the algorithm is simple enough, the indexes for a selected interleaver can be generated “on-the-fly”, as needed by the encoder and decoder, saving even more memory than if they had to be statically stored. On-the-fly index generation is considered a bonus feature since the overall memory requirements remain order KB, with or without this feature. However, this feature still reduces the amount of memory required and simplifies the initialization process when changing block lengths. Finally, the interleaver bank should provide good error rate performance for all block lengths.
There are well understood techniques used to design highly structured interleaver banks that satisfy all but the last of the above criteria. The challenge is to develop a design technique that yields good performance. For example, given a block length, K, a simple relative prime (RP) interleaver can be defined by just one other parameter, p, the modulo-K index increment. These interleavers can easily achieve high spreads and thus can eliminate the worst-case low-weight codewords. In fact, these interleavers do provide excellent performance for short block lengths. However, the performance for medium and long block lengths is poor because of the large number of compound low-weight codewords generated by the repetitive structure. Another example of a low-memory interleaver bank is that specified in the Third Generation Project Partnership (3GPP) standard. The 3GPP standard is used herein as one performance benchmark. Dithered-diagonal interleavers are also candidates for benchmarks. In particular, excellent performance results have been obtained for the special block lengths of K=2n2, where n is an integer, but not a multiple of the period of the feedback polynomial in the RSC encoders (e.g. 7 for 8-state RSC encoders). These special interleavers can be stored and implemented using just n index increment values. This represents a significant reduction in the memory requirements. However, the bank resolution is rather coarse and the block lengths are not the most convenient (e.g. they are generally not integer multiples of bytes).
Interleavers can be defined and implemented in a number of different ways. FIG. 2 shows the definition used here. The interleaver reads from a vector of input symbols or samples, vin 108, and writes to a vector of interleaved or permuted output samples, vout 110. The output samples 110 are written using the write indexes i=0 . . . K−1, where K is the interleaver length. Vector I defines the order that the samples are read from the input vector. That is, the i-th output, written to location i in the output vector, is read from location I(i) in the input vector. The interleaver is completely defined by read vector I. The elements being interleaved can be symbols used in an encoder, such as standard bits, or they can be signal samples or soft reliability values corresponding to transmitted symbols in a decoder. To be general, the symbols or samples will simply be referred to as elements. It is understood that interleavers are required in both encoders and decoders and that the term interleaver is also used to refer to a deinterleaver.
For example, letting [x]m denote x modulo-m arithmetic, a simple RP interleaver of length K is defined byI(i)=[s+ip]K, i=0 . . . K−1  (1)where p and K are relative primes and s is the starting index. Note that I can also be computed recursively using I(i)=[I(i−1)+p]K, i=1 . . . K−1  (2)where I(0)=s. Thus, an RP interleaver can be implemented using a single modulo-K index increment, p.The aforementioned new spread measure associated with two write indexes i and j, for any interleaver I, is defined asS″new(i, j)=|I(i)−I(j)|+|i−j|  (3)The (minimum) spread associated with index i is then                                           S            new            ′                    ⁡                      (            i            )                          =                              min                          j              ,                              j                ≠                i                                              ⁢                      [                                          S                new                ″                            ⁡                              (                                  i                  ,                  j                                )                                      ]                                              (        4        )            The overall (minimum) spread is defined as                               S          new                =                              min            i                    ⁢                      [                                          S                new                ′                            ⁡                              (                i                )                                      ]                                              (        5        )            
Proper termination of the Turbo-code's RSC constituent codes is very important for good performance at low error rates. Some form of dual termination or dual tail-biting is recommended for performance reasons. With dual tail-biting, the absolute differences in (3) should be computed in a tail-biting sense, as will be readily understood by one of skill in the art. For these spread definitions, it can be shown that the theoretical maximum spread (with dual tail-biting) is floor(√{square root over (2K)}). As an example, for a block length of K=512, the theoretical maximum spread is 32 (i.e. Snew≦32).
It is, therefore, desirable to provide a method of designing an interleaver that provides adequate packet error rate (PER) performance, good spread, and requires very little memory to store. Additional benefits of system granularity and the ability to generate the interleavers on-the-fly would also be advantageous to provide.